"""KMP算法，用于两个字符串的快速匹配，时间复杂度 O(n+m)
核心思想，
预先计算出，子串中，相同前后缀的长度的next数组，用于 如果当前字符不匹配，可以根据next数组跳过子串中前面已经匹配的字符，
不需要在从0开始遍历一个子串
同时遍历 主串和子串，分别为i,j， 当前遍历的字符有两种情况，
1.匹配 , i+=1,j+=1,遍历下一个字符
2.不匹配,根据next数组，跳过子串前面的一些字符

主串  ABABABCAA
子串  ABABC
next 00120
"""

def build_next(patt):
    """
    构建 next 数组，存储的是，如果后一个字符不匹配，子串可以跳出匹配的字符个数
    本质是，记录子串中，每个位置的公共前后缀的长度
    子串  ABACABAB
    next 00101232
    """
    next=[0]  # next 数组（初值元素一个0）
    prefix_len=0 # 当前共同前后缀的长度
    i=1   # 初始从第一个字符开始匹配
    while i<len(patt):
        if patt[prefix_len] == patt[i]:  # 代表可以构成一个更长的前后缀
            prefix_len+=1
            next.append(prefix_len)  # 先自加 prefix_len的值，后添加到数组中
            i+=1  # 向下一个字符匹配
        else:
            # 查表 依然不存在，next设为0
            if prefix_len == 0:
                next.append(0)
                i+=1  # 向下一个字符
            else:
                # 查表 看看其中存不存在更短的前后缀
                prefix_len = next[prefix_len-1]
    return next

def kmp(string,patt):
    next=build_next(patt)
    """
    主串  ABABABCAA
    子串  ABABC
    next 00120
    """
    j=0  # 主串中指针
    i=0  # 子串中的指针
    while i<len(string):
        if string[i]==patt[j]:  # 字符匹配，指针后移
            i+=1
            j+=1
        elif j>0:  # 字符不匹配，根据next 跳过子串前面的一些字符
            j=next[j-1]
        else:  # 子串第一个字符就不匹配
            i+=1
        if j==len(patt):  # 匹配成功，返回匹配的起始位置 or 根据题目实际情况返回
            return i-j
